/**
 * 最长连续序列
 *
 * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
 * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
 *
 * 示例 1：
 * 输入：nums = [100,4,200,1,3,2]
 * 输出：4
 * 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
 *
 * 示例 2：
 * 输入：nums = [0,3,7,2,5,8,4,6,0,1]
 * 输出：9
 *
 * 示例 3：
 * 输入：nums = [1,0,1,2]
 * 输出：3
 *
 * 提示：
 * 0 <= nums.length <= 105
 * -109 <= nums[i] <= 109
 */

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 这里我们使用两个 Map 记录每个位置的边界和最大连续数
 * 每次更新只需要更新最边界的就可以了
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(n)
 */

public class Main {
    public int longestConsecutive(int[] nums) {

        int n = nums.length;

        // 存这个数左右连续的最大长度的边界
        Map<Integer, int[]> map = new HashMap<>();
        // 存这个数的连续最大长度
        Map<Integer, Integer> hash = new HashMap<>();

        // 定义最后面的返回值
        int len = 0;

        for (int i = 0; i < n; i++) {

            // 把这个数定义出来, 后面方便使用
            int num = nums[i];

            // 如果已经处理过这个数了, 就跳过
            if (hash.containsKey(num)) {
                continue;
            }

            // 定义边界
            int leftLimit = num, rightLimit = num;

            // 观察是否存在旁边相邻的数, 有的话正好寻找边界
            if (hash.containsKey(num - 1)) {
                int[] left = map.get(num - 1);
                leftLimit = left[0];
            }

            if (hash.containsKey(num + 1)) {
                int[] right = map.get(num + 1);
                rightLimit = right[1];
            }

            // 更新边界
            int[] arr = new int[2];
            arr[0] = leftLimit;
            arr[1] = rightLimit;

            // 找边界的最大连续数
            int l = hash.getOrDefault(leftLimit, 0),
                    r = hash.getOrDefault(rightLimit, 0);


            // 更新最大连续数
            int k = l + r + 1;

            // 放入这个数
            map.put(num, arr);
            hash.put(num, k);

            // 防止边界数
            if (l != 0) {
                map.put(leftLimit, arr);
                hash.put(leftLimit, k);
            }

            if (r != 0) {
                map.put(rightLimit, arr);
                hash.put(rightLimit, k);
            }

            // 记录最大长度
            len = Math.max(len , k);
        }

        return len;
    }

    // 官方题解, 本题正解

    public int longestConsecutive2(int[] nums) {
        // 1. 放到集合里，方便 O(1) 判断
        Set<Integer> num_set = new HashSet<>();
        for (int num : nums) {
            num_set.add(num);
        }

        int longestStreak = 0;

        // 2. 遍历集合里的每个数
        for (int num : num_set) {
            // 2.1 如果 num-1 不在集合里，说明它是一个序列的起点
            if (!num_set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                // 2.2 一直往后找 num+1, num+2...
                while (num_set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                // 2.3 更新最大长度
                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }

    public static void main(String[] args) {
        Main test = new Main();
        int[] nums = new int[]{0,3,7,2,5,8,4,6,0,1};
        test.longestConsecutive(nums);
    }
}